package sort;

import java.util.*;
import java.util.stream.IntStream;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/14 15:19
 */
public class leetcode2501 {
    /*

   提供一下这样问题的思考方式
   从下标 index 开始 从 index  ~ len 的 范围内
   寻找 是否存在  container[index] = f( container(x) )
   x in index + 1 ~ len 之间
   这样的一个关系,那我们思考一下用 什么样的 容器 (数据结构)
   能够快速的 在 index + 1 ~ len 范围内 ,找到 是否存在 这样的一个 x
   哈希表
   题型: 两数 之 和 问题
     */

    public static int solution(int nums[]) {
        int len = nums.length;
//        IntStream stream = Arrays.stream(nums);
        Integer back[] = new Integer[len];
        for (int i = 0; i < len; i++)
            back[i] = i;
        Arrays.sort(back, (a, b) -> nums[a] - nums[b]);
        System.out.println(Arrays.toString(back));
// 通过 花费 o(n) 的代价 ,来获取 查询时候的一个  o(1) 的代价
        // 还需要 用到 index 索引 ,所以 这里使用 map
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : back)
            map.put(nums[i], i);

        int ans = 0;
        for (int i = 0; i < len; i++) {
            int compare = 0;
            int temp = nums[back[i]] * nums[back[i]];
            while (map.containsKey(temp)) {
                compare++;
                temp = temp * temp;
            }
            ans = Math.max(ans, compare);
        }
        return ans == 0 ? -1 : ans + 1;
    }

    public static void main(String[] args) {
//        int nums [] = {4,3,6,16,8,2};
        int nums [] = {18532,92682};
        int solution = solution(nums);
        System.err.println(solution);
        System.err.println(solutionOne(nums));
//        System.err.println(nums[0] * nums[0]);
//        Long l = new Long(12);
//        Long l1 = 12l;
//        Integer i = new Integer(12);
//        Integer i1 = 12;
//        System.out.println(i ==i1);
//        long l2 = 12;
//        System.out.println(l == l1);
//        Set<Integer> s1 = new HashSet<>();
//        s1.add(12);
//        System.out.println(s1.contains(i));
//
//        Set<Long> s3 = new HashSet<>();
//        s3.add(l);
//        System.out.println(s3.contains(l2));


    }

    /*
    上面这个 solution 考虑的情况 有点复杂
    其实考虑的有点多了

    因为 这个题 涉及 到 找到 一个子序列 还要进行 ** 重排 **
    这里的 重排 就很 骚,
    如果 一个 满足要求 的 子序列 , 顺序不对,那重排 依然是对的
    如果本来 就是有序的,那就不用考虑 index   下标
    所以 这道题 就变得的 很简单了
     */
    public static int solutionOne(int nums[]){
        int len = nums.length;
        // 还是 sort
        Arrays.sort(nums);
        Set<Integer> set = new HashSet<>(len);
        for(int num : nums)
            set.add(num);
        int ans = 0;
        for(int num : nums){
            int compare = 0;
            long temp = (long)num * num;
            if(temp > 100000)
                continue;
            while (set.contains((int)temp)){
                compare ++;
                temp = temp * temp;
            }
            ans = Math.max(ans,compare);
        }
        return ans == 0 ?  -1 : ans + 1 ;
    }
    /*
    你会发现这个 题如果思考明白的话 就会非常的 简单,而且思路 也很多
    同时也要注意 一下这个 包装类 的自动拆箱 和 装箱的 这种 小的细节
     */
    public int solutionFinally(int nums[]){
        /*
         采用  倒序遍历 ,会更加的 优雅
         看到一个题的 最先 观察的 就是 数据范围
         这个题 最大的收获 就是 这一点,数据的范围的分析
         */
        int ans = 0;

//        Set<Integer> set = new HashSet<>();
        /*
        另外一种写法就是 把 map 用数组 来代替,用数组 来模拟 map
        这个题说实话,学到的东西 还不少
         */
        Map<Integer,Integer> map = new HashMap<>();
        Arrays.sort(nums);
        for(int i = nums.length - 1;i >= 0;i--){
//            int compare =  0;
            long temp = (long)nums[i] * nums[i];

            map.put(nums[i],temp > 100000 ? 0 : map.getOrDefault((int)temp,0) + 1);
            ans = Math.max(ans,map.get(nums[i]));

        }
        return ans;
    }

}
